package org.xingole.leetcode.dp.grid;

import java.util.Arrays;

/*
 * Problem:
 *  
 * You are given an 'n x n' 'grid' representing a feild of cherries, each cell is one
 * of three possible integers.
 * 
 * - 0 means the cell is empty, so you can pass through,
 * - 1 means the cell contains a cherry that you can pick up and pass through, or
 * - -1 means the cell contains a thorn that blocks your way.
 * 
 * Return the maximum number of cherries you can collect by following the rules below:
 * 
 * - Starting at the position '(0, 0)' and reaching to '(n-1, n-1)' by moving right or
 * down through valid path cells ( cells with value 0 or 1).
 * - After reading '(n-1, n-1)', returning to '(0, 0)' by moving left or up through 
 * valid path cells.
 * - When passing through a path cell cotaining a cherry, you pick it up, and the cell
 * becomes an empty cell 0.
 * - If there is no valid path between '(0, 0)' and '(n - 1, n - 1)', then no cherries
 * can be collected.
 * 
 */

public class CherryPickup {

     /*
      * Approach : Dynamic Programming
      * 
      * Instreand of walking from end to beginning, let's reverse the second leg of the 
      * path, so we are only considering two paths from beginning to the end.
      *   
      * Let's say they both start at the same time, at the same speed.
      * Notice after t steps, each position (r, c) we could be, is on the line r + c = t.
      * So if we have two pepole at positoins (r1, c1) and (r2, c2), then r2 + c2 = r1 + c1 = t.
      * That means the variables r1, c1, c2 uniquely determine 2 people who have walked the 
      * same r1 + c1 number of steps. This sets up for dynamic programming quite nicely.
      *
      * Let dp[t][r1][r2] be the most number of cherries obtained by two people targeted
      * at (r1, c1) and (r2, c2) and walking from (0,0) picking up cherries, where
      * c1 = t - r1, and c2 = t - r2, t reprents the both robots need move t steps to 
      * arrive the (r1, c1) and (r2, c2) repspectively.
      *
      * Therefore the ultimate answer is  max(dp[2*n-2][n-1][n-1], 0).
      *
      * if grid[r1][c1] or grid[r2][c2] are thorns, then 
      *    dp[t][r1][r2] = -infinity
      *
      * if grid[r1][c1] and grid[r2][c2] are not thorns, 
      *
      * There 4 possibilities for person 1 and 2 moving down and right:
      * 1. Person 1 down and person 2 down : dp[t-1][r1-1][r2-1]
      * 2. Person 1 right and person 2 down : dp[t-1][r1][r2-1]
      * 3. Person 1 down and person 2 right : dp[t-1][r1-1][r2]
      * 4. Person 1 right and person 1 right : dp[t-1][r1][r2]
      * 
      * Therefore, dp[t][r1][r2] = max(case 1, case 2, case 3, case 4) + value(r1, c1, r2, c2)
      * where 
      *      value(r1, c1, r2, c2) = grid[r1][c1] + grid[r2][c2], if r1 != r2;
      *      value(r1, c1, r2, c2) = grid[r1][c1],                if r1 == r2;
      * 
      */
     private static final int NEG_INF = Integer.MIN_VALUE; // no solution cases.

     public int cherryPickup(int[][] grid) {
          int n = grid.length;
          int steps = 2 * n - 2;
 
          int[][][] dp = new int[steps + 1][n][n];

          for ( int[][] table : dp) {
               for ( int[] record : table ) {
                    Arrays.fill(record, NEG_INF);
               }
          }

          // base case:
          dp[0][0][0] = grid[0][0];

          // we can keep r1 <= r2 for conveience.
          for ( int t = 1; t <= steps; ++t ) {
               
               // robot 1 starting at (r1, t - r1)
               for ( int r1 = Math.max(0, t - (n - 1) ); r1 <= Math.min(n - 1, t); ++r1 ) {

                    int c1 = t - r1;
                    if ( grid[r1][c1] == -1 ) {
                         continue;
                    }

                    for ( int r2 = r1; r2 <= Math.min(n-1, t); ++r2 ) {
                         int c2 = t - r2;

                         if ( grid[r2][c2] == -1 ) {
                              continue;
                         }

                         // state transfer
                         int max = dp[t - 1][r1][r2];  // both right
                         
                         if ( r1 > 0 ) {
                              max = Math.max(max, dp[t-1][r1-1][r2]); // down, right
                         } 
                         if ( r2 > 0 ) {
                              max = Math.max(max, dp[t-1][r1][r2-1]);  // right, down
                         }
                         if ( r1 > 0 && r2 > 0 ) {
                              max = Math.max(max, dp[t-1][r1-1][r2-1]); // both down
                         }

                         max += grid[r1][c1];
                         if ( r1 != r2 ) {
                              max += grid[r2][c2];
                         }

                         dp[t][r1][r2] = max;
                    }

               }
          }

          return Math.max(dp[steps][n-1][n-1], 0);
     }

}
